import java.util.Arrays;

public class mergesort {
    public static int[] arr={1,34,23,565,44,32,5,8,56,4,9};
    public static int[] helper=new int[arr.length];
    public static void mergesort(int[] arr,int a,int b){//归并排序
        if(a<b){
            int mid=a+((b-a)>>1);
            mergesort(arr,mid+1,b);
            mergesort(arr,a,mid);
            merge(arr,mid,a,b);
        }

    }

    public static void merge(int[] arr,int mid,int a,int b){
        for (int i = 0; i <arr.length ; i++) {
            helper[i]=arr[i];
        }
        int left=a;//左指针
        int right=mid+1;//右指针
        int point=a;//替换数据指针
        while(left<mid+1&&right<=b){
            if(helper[left]<=helper[right]){
                arr[point]=helper[left];
                point++;
                left++;
            }else{
                arr[point]=helper[right];
                point++;
                right++;
            }
        }
        while(left<mid+1){
            arr[point]=helper[left];
                    point++;
                    left++;
        }
    }
    public static void main(String args[]){
        mergesort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
